{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "但凡说起分布式系统，我们肯定会对一些海量级的业务进行分拆，比如：用户表，订单表。因为数据量巨大一张表完全无法支撑，就会对其进行分库分表。但是一旦涉及到分库分表，就会引申出分布式系统中唯一主键ID的生成问题，当我们使用mysql的自增长主键(auto_increment)时，充分感受到了它的好处：整个系统ID唯一，ID是数字类型，而且是趋势递增的，ID简短，查询效率快，在分布式系统中显然由于单点问题无法使用mysql自增长了，此时需要别的解决方案来支撑分布式业务。\n",
    "\n",
    "---\n",
    "\n",
    "首先映入脑海的一定是uuid"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# UUID\n",
    "\n",
    "python有一个模块叫做uuid，导入它就可以使用它的四个方法了。注意这四个方法依次是`uuid1()`, `uuid3()`, `uuid4()`, `uuid5()`, \n",
    "然而并没有`uuid2()`。\n",
    "\n",
    "## 优点：\n",
    "\n",
    "1. 简单，代码方便。\n",
    "2. 生成ID性能非常好，基本不会有性能问题。\n",
    "3. 全球唯一，在遇见数据迁移，系统数据合并，或者数据库变更等情况下，可以从容应对。\n",
    "\n",
    "## 缺点：\n",
    "\n",
    "1. 没有排序，无法保证趋势递增。\n",
    "2. UUID往往是使用字符串存储，查询的效率比较低。\n",
    "3. 存储空间比较大，如果是海量数据库，就需要考虑存储量的问题。\n",
    "4. 传输数据量大\n",
    "5. 不可读\n",
    "\n",
    "## python 中的uuid"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "f0ef691e-f0e7-11ea-80d5-f01898013ebb\n"
     ]
    }
   ],
   "source": [
    "# -*- coding:utf-8 -*-\n",
    "import uuid\n",
    " \n",
    "print(uuid.uuid1())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "f6775bf3-2c41-322d-b441-1b591e5cf4ab\n"
     ]
    }
   ],
   "source": [
    "print(uuid.uuid3(uuid.NAMESPACE_DNS, 'wzz'))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "5748f7e5-a6c9-434c-93b6-44813a6d30dd\n"
     ]
    }
   ],
   "source": [
    "print(uuid.uuid4())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "709013d6-53c9-5b89-8b41-b1ffadf96ece\n"
     ]
    }
   ],
   "source": [
    "print(uuid.uuid5(uuid.NAMESPACE_DNS, 'wzz'))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "乍一看全都是36个字符，那么他们到底有什么不同呢，下面一一分析。\n",
    "\n",
    "- `uuid1`：这个是根据当前的**时间戳和MAC地址**生成的，最后的12个字符408d5c985711对应的就是MAC地址，因为是MAC地址，那么唯一性应该不用说了。但是生成后暴露了MAC地址这就很不好了。\n",
    "\n",
    "- `uuid3`：里面的namespace和具体的字符串都是我们指定的，然后呢···应该是通过MD5生成的，这个我们也很少用到，莫名其妙的感觉。\n",
    "\n",
    "- `uuid4`：这是基于随机数的uuid，既然是随机就有可能真的遇到相同的，但这就像中奖似的，几率超小，因为是随机而且使用还方便，所以使用这个的还是比较多的。\n",
    "\n",
    "- `uuid5`：这个看起来和uuid3()貌似并没有什么不同，写法一样，也是由用户来指定namespace和字符串，不过这里用的散列并不是MD5，而是SHA1.\n",
    "\n",
    "下面再来说一下简单的处理，UUID中间的'-'是个比较奇怪的字符，那么应该去掉它，这其实超简单："
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "'9067eee9e18d4bb49d9d7cdfef059b43'"
      ]
     },
     "execution_count": 18,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "uid = uuid.uuid4()\n",
    "uid.hex"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 变种的UUID\n",
    "\n",
    "1）为了解决UUID不可读，可以使用UUID to Int64的方法。\n",
    "\n",
    "2）为了解决UUID无序的问题，NHibernate在其主键生成方式中提供了Comb算法（combined guid/timestamp）。保留GUID的10个字节，用另6个字节表示GUID生成的时间（DateTime）。\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "---\n",
    "\n",
    "# SnowFlake 雪花算法\n",
    "\n",
    "客观地说，如果一定要用uuid生成订单号这类东西也能凑合用，但是它有着罄竹难书的“罪行”：**肉眼可见，它是无序的**；长度是64位数字字母随机组合的字符串，**占用空间巨大**；完全不具备业务属性，也就是说使用uuid你完全无法推算出它到底是干嘛的；因为无序，所以趋势递增就更不用指望了；所以用uuid生成订单号就是自杀行为，**适合它的是类似生成token令牌的场景**。\n",
    "\n",
    "那么我们就要说起业界鼎鼎有名的SnowFlake(雪花算法)发号器了。 Twitter-Snowflake算法产生的背景相当简单，为了满足Twitter每秒上万条消息的请求，每条消息都必须分配一条唯一的id，这些id还需要一些大致的顺序，让twitter可以通过一定的索引来进行检索，而在Twitter庞大的分布式系统中不同机器产生的id必须又必须不同。\n",
    "\n",
    "它的好处显而易见，**不仅全局唯一，并且有序按时间递增，同时占用空间少，生成的id仅仅是19位的整形数字**，正好契合mysql的bigint数据类型，简直完美。\n",
    "\n",
    "为啥它叫做Snowflake(雪花)算法？因为每个人都知道没有两片一样的雪花，这一事实源于晶体在天空中形成的方式。雪是一团冰晶，在大气中形成，并在它们下落时保持其形状。雪花形成于大气冷到能阻止它们融化变成雨或雨夹雪的时候。尽管云中的温度和湿度是不均匀的，但是在雪花大小的范围内，这些变量大约都是常数，这就是雪花的生长通常是对称的原因。另一方面，塔夫茨大学（Tufts University）化学家玛丽·简·舒尔茨（Mary Jane Shultz）指出：每片雪花都受到风，日光和其他变量变化的影响。她解释说，由于每个雪晶都到云层紊乱的影响，它们的形式都略有不同。\n",
    "\n",
    "而Snowflake的逻辑也非常简单，**雪花算法生成64位的二进制正整数，然后转换成10进制的数**。64位二进制数由如下部分组成：\n",
    "\n",
    "![](../assets/snowflake.png)\n",
    "\n",
    "- 1位标识符：始终是0\n",
    "\n",
    "- 41位时间戳：41位时间戳不是存储当前时间的时间戳，而是存储时间截的差值（当前时间截 - 开始时间截 )得到的值，这里的的开始时间截，一般是我们的id生成器开始使用的时间，由我们程序来指定的\n",
    "- 10位机器标识码：可以部署在1024个节点，如果机器分机房（IDC）部署，这10位可以由 5位机房ID + 5位机器ID 组成\n",
    "- 12位序列：毫秒内的计数，12位的计数顺序号支持每个节点每毫秒(同一机器，同一时间截)产生4096个ID序号\n",
    "\n",
    "看到时间戳，就可以联想到它的缺陷，也就是它依赖机器的时钟，如果服务器时钟回拨，可能会导致重复ID生成。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## java 实现源码\n",
    "\n",
    "- http://www.blogjava.net/bolo/archive/2015/07/13/426200.html"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 在python使用\n",
    "\n",
    "这里我们用Python3.0来生成SnowFlake生成的唯一id\n",
    "\n",
    "首先安装库\n",
    "\n",
    "```sh\n",
    "pip3 install pysnowflake\n",
    "```\n",
    "\n",
    "安装完成后，就可以在本地命令行启动snowflake服务\n",
    "\n",
    "```sh\n",
    "snowflake_start_server --worker=2\n",
    "```\n",
    "\n",
    "这里的worker就是当前节点的标识，此时编写代码就可以打印出当前客户端使用的snowflake的服务信息\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "如果一台服务器上起了很多节点服务，也可以指定相关的节点进行装载"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "scrolled": true
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "{'dc': 0, 'worker': 2, 'timestamp': 1603889846340, 'last_timestamp': 1603889346231, 'sequence': 1, 'sequence_overload': 0, 'errors': 0}\n"
     ]
    }
   ],
   "source": [
    "import snowflake.client\n",
    "print(snowflake.client.get_stats())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "host = '127.0.0.1'\n",
    "port = 8910\n",
    "snowflake.client.setup(host, port)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "4419153299287056385\n"
     ]
    }
   ],
   "source": [
    "import snowflake.client\n",
    "print(snowflake.client.get_guid())"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "可以看到这些id很明显带有递增的连续性，有的人会问了，假设我搭建了上千个节点的分布式系统，此时接口接到参数id,我怎么判断该id的订单信息存储在那个节点中呢？\n",
    "\n",
    "其实很容易就可以判断，从SnowFlake的算法结构入手，本身就是二进制转换十进制的整形，现在我们反着进行解析即可，这里以这个19位的id为例子：4400679418666688513\n",
    "\n",
    "首先将其转换为二进制"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 33,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "'0b11110100010010010110101001110110010000000000000010000000000001'"
      ]
     },
     "execution_count": 33,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "bin(4400679418666688513)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "可以看到上文所述的第一位是标识符，此后是41位的时间戳，紧接着10位的节点标识码，最后12位的递增序列，从后面数12位是：000000000001，倒数5位是：00001  这5位就是某个节点的存储标识，但是它目前是二进制，我们再将它转换为十进制\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 29,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "1"
      ]
     },
     "execution_count": 29,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "int('00001',2)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "可以看到，转换结果显示该id存储在节点1的数据库中，如此就具备了相当强的业务属性，通过反推逻辑我们可以快速准确的定位到数据的具体存储位置从而进行查询。\n",
    "\n",
    "# 结语\n",
    "\n",
    "其实关于分布式唯一id的解决方案，也不仅仅只有uuid或者snowflake，像**redis的incr原子性操作自增**，亦或者**Mongodb极具特色的Objectid**的生成方式，专为分布式而设计的ID生成方案。都是可以参考的解决方案，但是方案总归是方案，总有其自身的特点和缺陷，这就需要根据实际应用场景而具体问题进行具体分析了。\n",
    "\n",
    "\n",
    "**原文参考**\n",
    "\n",
    "- https://v3u.cn/a_id_155\n",
    "- https://zhuanlan.zhihu.com/p/42065647\n",
    "- https://zhuanlan.zhihu.com/p/152179727"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.7.3"
  },
  "toc": {
   "base_numbering": 1,
   "nav_menu": {},
   "number_sections": true,
   "sideBar": true,
   "skip_h1_title": false,
   "title_cell": "Table of Contents",
   "title_sidebar": "Contents",
   "toc_cell": false,
   "toc_position": {
    "height": "calc(100% - 180px)",
    "left": "10px",
    "top": "150px",
    "width": "175px"
   },
   "toc_section_display": true,
   "toc_window_display": true
  },
  "varInspector": {
   "cols": {
    "lenName": 16,
    "lenType": 16,
    "lenVar": 40
   },
   "kernels_config": {
    "python": {
     "delete_cmd_postfix": "",
     "delete_cmd_prefix": "del ",
     "library": "var_list.py",
     "varRefreshCmd": "print(var_dic_list())"
    },
    "r": {
     "delete_cmd_postfix": ") ",
     "delete_cmd_prefix": "rm(",
     "library": "var_list.r",
     "varRefreshCmd": "cat(var_dic_list()) "
    }
   },
   "types_to_exclude": [
    "module",
    "function",
    "builtin_function_or_method",
    "instance",
    "_Feature"
   ],
   "window_display": false
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}
